{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "cryptanalysis-of-RSA.ipynb",
      "version": "0.3.2",
      "provenance": [],
      "collapsed_sections": [],
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "accelerator": "GPU"
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/TerenceLiu98/Algorithm/blob/master/cryptanalysis_of_RSA.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "DVsOab0BcLf5",
        "colab_type": "text"
      },
      "source": [
        "## RSA Cryptosystem \n",
        "\n",
        "使得 $N = pq$ 是两个大质数 $p$ 和 $q$的乘积，使得 $P = C = Z_N$（以 $N$ 为模），定义密钥空间为:\n",
        "<br><br>\n",
        "$$K = \\{(N, p, q, e, d): ed \\equiv 1 \\ (mod \\ \\phi(N))\\}$$\n",
        "<br>\n",
        "其中，$\\phi(N) = (p - 1)(q - 1)$ （*参见欧拉$\\phi$函数* ）\n",
        "\n",
        "* 加密：$enc_K(x) = x^e \\ mod \\ N$\n",
        "* 解密：$dec_K(y) = y^d \\ mod \\ N$\n",
        "\n",
        "* RSA 方程： $gcd(e, \\phi(N)) = 1 \\Rightarrow ed \\equiv 1 \\ (mod \\ \\phi(N)) \\Rightarrow ed = 1 + k \\phi(N)$\n",
        "* RSA 模数：$N = p q$ \n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "rBUUQ1QffIsR",
        "colab_type": "text"
      },
      "source": [
        "## 如何生成大素数\n",
        "\n",
        "### 素性测试\n",
        "\n",
        "如果数字小，我们可以用枚举法，也就是俗称的「暴力破解」可解，可以写一个循环从$2$开始一直除到$n - 1$（实际上 $\\sqrt{n}$即可），如果其中有数可以整除 $n$， 则 $n$ 不是素数。\n",
        "\n",
        "第一种：$n$\n",
        "\n",
        "```python \n",
        "import datetime \n",
        "start = datetime.datetime.now()\n",
        "a = 0\n",
        "\n",
        "for n in range(2, 50000):\n",
        "    for x in range(2, n):\n",
        "        if n % x == 0:\n",
        "            break\n",
        "    else:\n",
        "        # loop fell through without finding a factor\n",
        "        # print(n)\n",
        "        a = a + 1\n",
        "\n",
        "end = datetime.datetime.now() \n",
        "time = end - start\n",
        "print(time, a)\n",
        "```\n",
        " \n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "9y7DXjTrgcCU",
        "colab_type": "code",
        "outputId": "4c5c1b76-742d-4035-8f24-6c32f4564a61",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "import datetime \n",
        "start = datetime.datetime.now()\n",
        "a = 0\n",
        "\n",
        "for n in range(2, 50000):\n",
        "    for x in range(2, n):\n",
        "        if n % x == 0:\n",
        "            break\n",
        "    else:\n",
        "        # loop fell through without finding a factor\n",
        "        # print(n)\n",
        "        a = a + 1\n",
        "\n",
        "end = datetime.datetime.now() \n",
        "time = end - start\n",
        "print(time, a)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "0:00:13.897045 5133\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "biUbU5nbhf2n",
        "colab_type": "text"
      },
      "source": [
        "### 费马小定理\n",
        "\n",
        "> 费马小定理是数论中的一个定理：假设 $a$ 是一个整数，$p$ 是一个质数，那么 $a^p - a$ 是 $p$ 的倍数，可以表示为：$a^p \\equiv a \\ (mod \\ p)$(同余：余数相同)；如果 $a$ 不是 $p$ 的倍数，这个定理也可以写成：$a^{p - 1} \\equiv 1 \\ (mod \\ p)$\n",
        ">\n",
        "> 来源：维基百科\n",
        "\n",
        "* 如果 $x$ 和 $y$ 的最大公约数为 $1$，则称：$x$ 和 $y$ 互素 (coprime)\n",
        "\n",
        "* 根据费马小定理：$a(a^{p - 1} - 1)$ 是 $p$ 的倍数，所以，当 $a$ 不是 $p$ 的倍数时， $a^{p - 1} - 1$ 是 $p$ 的倍数 $\\Rightarrow a^{p - 1} \\equiv 1 \\ (mod \\ p)$ \n",
        "* 费马小定理为判定一个数是否为素数的**必要条件**，并非充分条件，就是说存在**伪素数**满足费马小定理却不是素数，例如：$2^340 \\equiv 1 \\ (mod \\ 341)$，但是 $341 = 11 \\times 31$\n",
        "\n",
        "### 欧拉出现 -- 费马欧拉定理\n",
        "\n",
        "* $a$ 和 $n$ 互素：$a \\bot n \\Rightarrow a^{\\phi n} \\equiv 1 \\ (mod \\ n) \\textbf{ 费马欧拉定理 }; \\phi(an) - \\phi(m)\\phi(n)$\n",
        "* 当 $n$为质数时， $\\phi n = (n - 1)$ 所以，$a^{\\phi n} \\equiv 1 \\ (mod \\ n) \\Rightarrow a^{n - 1} \\equiv 1 \\ (mod \\ n)$ 也就是费马小定理\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "W3PNd8zWqThA",
        "colab_type": "text"
      },
      "source": [
        "### 费马素性检验\n",
        "\n",
        "根据费马小定理，如果我们检验的 $a$ 越多，得到素数的概率会越大，但是得到合数的概率却不可能等于 $0$。 所以，我们称这些数是伪素数(pseudo-prime)\n",
        "\n",
        "```python\n",
        "ddef fermat_prime_test(n, k):\n",
        "  if n == 2:\n",
        "    print(n, \"n is a composite\")\n",
        "  \n",
        "  if n % 2 == 0:\n",
        "    print(n, \"n is a composite\")\n",
        "  \n",
        "  for i in range(k):\n",
        "    a = random.randint(1, n-1)\n",
        "    if pow(a, n - 1) % n != 1:\n",
        "      print(n, \"n is a composite\")\n",
        "      break\n",
        "      \n",
        "  return True\n",
        "      "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "LWX2rNijhfnT",
        "colab_type": "code",
        "outputId": "46cb7f08-7b30-4829-cc2f-896370410580",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 51
        }
      },
      "source": [
        "def fermat_prime_test(n, k):\n",
        "  import random\n",
        "  \n",
        "  if n == 2:\n",
        "    print(n, \"n is a composite\")\n",
        "  \n",
        "  if n % 2 == 0:\n",
        "    print(n, \"n is a composite\")\n",
        "  \n",
        "  for i in range(k):\n",
        "    a = random.randint(1, n-1)\n",
        "    if pow(a, n - 1) % n != 1:\n",
        "      print(n, \"n is a composite\")\n",
        "      break\n",
        "      \n",
        "  return 0\n",
        "\n",
        "fermat_prime_test(6789865, 6789865)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "6789865 n is a composite\n"
          ],
          "name": "stdout"
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "0"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 2
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "-dUWQqgavi5S",
        "colab_type": "text"
      },
      "source": [
        "### Miller-Rabin 素性测试 (probably prime)\n",
        "\n",
        "基于费马小定理的二次探测定理：\n",
        "\n",
        "1. Find $n - 1 = 2^k \\times m$\n",
        "2. choose $a: 1 < a < n - 1$\n",
        "3. compute $b_0 = a^m \\ (mod \\ n), b_i = b_{i - 1}^2$\n",
        "\n",
        "\n",
        "例子： Is $53$ prime? \n",
        "\n",
        "1. $n = 53 \\Rightarrow n - 1 = 52; \\frac{52}{2^1} = 26; \\frac{52}{2^2} = 13; \\frac{52}{2^3} = 6.5 \\Rightarrow $ We choose $52 = 2^2 \\times 13 \\Rightarrow k = 2, m = 13$\n",
        "\n",
        "2. $a$ is from $1$ to $52$, we can just choose $a = 2$ \n",
        "3. $b_0 = 2^{13} \\ mod \\ 53 \\Rightarrow b_0 = 30 \\neq (1 \\ mod \\ 53) \\neq (- 1 \\ mod \\ 53)$\n",
        "4. $b_1 = 30^2 \\ mod \\ 53 = -1 \\ mod \\ 53 = 52 \\Rightarrow \\textbf{probably prime}$\n",
        "\n",
        "```\n",
        "Input: n > 2, an odd integer to be tested for primality;\n",
        "       k, a parameter that determines the accuracy of the test\n",
        "Output: composite if n is composite, otherwise probably prime\n",
        "write n − 1 as 2s·d with d odd by factoring powers of 2 from n − 1\n",
        "LOOP: repeat k times:\n",
        "   pick a randomly in the range [2, n − 1]\n",
        "   x ← ad mod n\n",
        "   if x = 1 or x = n − 1 then do next LOOP\n",
        "   for r = 1 .. s − 1\n",
        "      x ← x2 mod n\n",
        "      if x = 1 then return composite\n",
        "      if x = n − 1 then do next LOOP\n",
        "   return composite\n",
        "return probably prime\n",
        "```\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "r3uig_6bT7uI",
        "colab_type": "code",
        "outputId": "63dd29a7-7999-4f6f-b16d-108f598bea5a",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "def miller_rabin(n, k):\n",
        "    \n",
        "    import random \n",
        "\n",
        "    if n == 2:\n",
        "        return True\n",
        "\n",
        "    if n % 2 == 0:\n",
        "        return False\n",
        "\n",
        "    r, s = 0, n - 1\n",
        "    while s % 2 == 0:\n",
        "        r += 1\n",
        "        s //= 2\n",
        "    for _ in range(k):\n",
        "        a = random.randrange(2, n - 1)\n",
        "        x = pow(a, s, n)\n",
        "        if x == 1 or x == n - 1:\n",
        "            continue\n",
        "        for _ in range(r - 1):\n",
        "            x = pow(x, 2, n)\n",
        "            if x == n - 1:\n",
        "                break\n",
        "        else:\n",
        "            return False\n",
        "    return True\n",
        "  \n",
        "miller_rabin(56787641, 7890)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "False"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 19
        }
      ]
    }
  ]
}